# 前K个高频元素： https://leetcode-cn.com/problems/top-k-frequent-elements/submissions/

class Solution:
    def topKFrequent(self, nums: list, k: int) -> list:
        """
            和 215号算法题，数组中第k个最大元素，一样。 只是需要使用字典统计频率
            根据进阶版的提示， 时间复杂度 必须 优于 O(n log n)，且 寻找前k个高频的数，那么
            可以想到使用堆来解决， 时间复杂度一般为 O(nlogK). 并且元素无序。
        """
        # 1. 先使用一个一个字典用来统计数的频率
        freq = dict()
        for num in nums: 
            freq[num] = freq.get(num, 0) + 1
        
        # 2. 使用最小堆
        def heapqAdjust(nums):
            """ 调整堆， 比较大小需要使用 freq的value """
            n = len(nums)
            i = 0
            end = n - 1
            r = nums[0]
            rc = freq.get(nums[0])
            while i * 2 + 1 <= end:
                j = i * 2 + 1
                if j < end and freq.get(nums[j]) > freq.get(nums[j + 1]): j += 1
                if freq.get(nums[j]) > rc: break
                nums[i] = nums[j]
                i = j
            
            nums[i] = r
        
        def heapqPush(nums, num):
            """ 添加元素进堆 """
            nums.append(num)
            n = len(nums)
            i = n - 1
            while (i - 1) // 2 >= 0:
                j = (i - 1) // 2
                if freq.get(nums[j]) < freq.get(num): break
                nums[i] = nums[j]
                i = j

            nums[i] = num

        # 3. 开始逻辑
        heap = []
        for num in freq.keys():
            if len(heap) < k:
                heapqPush(heap, num)

            elif freq.get(num) > freq.get(heap[0]):
                heap[0] = num
                heapqAdjust(heap)

        return heap

